package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 面试题 17.13. 恢复空格
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/18 16:59
 */
public class Respace {

    public static void main(String[] args) {
        Respace test = new Respace();
        String[] arr = {"looked", "just", "like", "her", "brother"};
        String str = "jesslookedjustliketimherbrother";
        test.respace(arr, str);
    }

    public int respace(String[] dictionary, String sentence) {
        int m = sentence.length();
        int[] dp = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            for (String word : dictionary) {
                int len = word.length();
                if (i >= len && word.equals(sentence.substring(i - len, i))) {
                    dp[i] = Math.max(dp[i], dp[i - len] + len);
                } else {
                    dp[i] = Math.max(dp[i], dp[i - 1]);
                }
            }
        }
        return m - dp[m];
    }

}
